#include <list>
#include <iostream>
#include <algorithm>

using namespace std;

// merge b into a
list<int> & merge(list<int> a, list<int> b)
{
    list<int>::iterator i;
    list<int>::iterator j;

    for (i = a.begin(), j = b.begin();
            i != a.end() && j != b.end();
        )
    {
        if (*i < *j)
        {
            i++;
        }
        else
        {
            a.insert(i, *j++);
        }
    }

    if (j != b.end())
    {
        while (j != b.end())
            a.insert(i, *j++);
    }

    return a;
}

void print_list(list<int> l)
{
    for (list<int>::iterator i = l.begin();
            i != l.end();
            i++)
    {
        cout << *i << '\t';
    }
    cout << endl;
}

int main()
{
    srand(time(NULL));

    list<int> a;
    list<int> b;
    
    for (int i = 0; i < rand() % 11 + 3; i++)
    {
        a.push_back(rand() % 37);
    }
    a.sort();
    for (int i = 0; i < rand() % 13; i++)
    {
        b.push_back(rand() % 41);
    }
    b.sort();

    print_list(a);
    print_list(b);

    a = merge(a, b);

    print_list(a);
    //print_list(b);
}
